package com.test;

/**
 * 希尔排序
 *
 * 时间复杂度o(n`1.2)
 *
 * 说明:
 * 算法先将要排序的一组数按照某个增量d(n/2 , m为要排序的个数)分为若干组 ， 每组中记录的下标相差d，
 * 对每组中全部元素进行直接插入排序。然后再用一个较小的增量(d/2)对它进行分组，在每组中再进行插入排序。
 * 当增量减少到1的时候，进行直接插入排序后。排序完成。
 *
 *
 * Created by abing on 2015/11/26.
 */
public class SuanFaHill {

    public static void main(String[] args){
        int[] arr = {1,8,4,2,6,12,34,21,33,55,11,88,33};
        sort(arr);

    }

    public static void sort(int[] arr){
        double d1 = arr.length;
        int tmp = 0 ;
        while (true) {
            d1 = Math.ceil(d1/2);
            int d = (int) d1;
            for (int x = 0 ; x < d ; x++){
                for (int i = x+d ; i < arr.length ; i+=d){
                    int j = i -d;
                    tmp = arr[i];
                    while (j >=0 && tmp <arr[j]){
                        arr[j+d] = arr[j];
                        j -=d;
                    }
                    arr[j+d] = tmp;
                }
            }
            if (d == 1){
                break;
            }
        }

        for (int a : arr){
            System.out.print(a + " ");
        }

    }
}
